// CodeMirror, copyright (c) by Marijn Haverbeke and others
// Distributed under an MIT license: https://codemirror.net/LICENSE

(function(mod) {
    if (typeof exports == "object" && typeof module == "object") // CommonJS
      mod(require("../../lib/codemirror"))
    else if (typeof define == "function" && define.amd) // AMD
      define(["../../lib/codemirror"], mod)
    else // Plain browser env
      mod(CodeMirror)
  })(function(CodeMirror) {
    "use strict"
    var Pos = CodeMirror.Pos
  
    function regexpFlags(regexp) {
      var flags = regexp.flags
      return flags != null ? flags : (regexp.ignoreCase ? "i" : "")
        + (regexp.global ? "g" : "")
        + (regexp.multiline ? "m" : "")
    }
  
    function ensureFlags(regexp, flags) {
      var current = regexpFlags(regexp), target = current
      for (var i = 0; i < flags.length; i++) if (target.indexOf(flags.charAt(i)) == -1)
        target += flags.charAt(i)
      return current == target ? regexp : new RegExp(regexp.source, target)
    }
  
    function maybeMultiline(regexp) {
      return /\\s|\\n|\n|\\W|\\D|\[\^/.test(regexp.source)
    }
  
    function searchRegexpForward(doc, regexp, start) {
      regexp = ensureFlags(regexp, "g")
      for (var line = start.line, ch = start.ch, last = doc.lastLine(); line <= last; line++, ch = 0) {
        regexp.lastIndex = ch
        var string = doc.getLine(line), match = regexp.exec(string)
        if (match)
          return {from: Pos(line, match.index),
                  to: Pos(line, match.index + match[0].length),
                  match: match}
      }
    }
  
    function searchRegexpForwardMultiline(doc, regexp, start) {
      if (!maybeMultiline(regexp)) return searchRegexpForward(doc, regexp, start)
  
      regexp = ensureFlags(regexp, "gm")
      var string, chunk = 1
      for (var line = start.line, last = doc.lastLine(); line <= last;) {
        // This grows the search buffer in exponentially-sized chunks
        // between matches, so that nearby matches are fast and don't
        // require concatenating the whole document (in case we're
        // searching for something that has tons of matches), but at the
        // same time, the amount of retries is limited.
        for (var i = 0; i < chunk; i++) {
          if (line > last) break
          var curLine = doc.getLine(line++)
          string = string == null ? curLine : string + "\n" + curLine
        }
        chunk = chunk * 2
        regexp.lastIndex = start.ch
        var match = regexp.exec(string)
        if (match) {
          var before = string.slice(0, match.index).split("\n"), inside = match[0].split("\n")
          var startLine = start.line + before.length - 1, startCh = before[before.length - 1].length
          return {from: Pos(startLine, startCh),
                  to: Pos(startLine + inside.length - 1,
                          inside.length == 1 ? startCh + inside[0].length : inside[inside.length - 1].length),
                  match: match}
        }
      }
    }
  
    function lastMatchIn(string, regexp, endMargin) {
      var match, from = 0
      while (from <= string.length) {
        regexp.lastIndex = from
        var newMatch = regexp.exec(string)
        if (!newMatch) break
        var end = newMatch.index + newMatch[0].length
        if (end > string.length - endMargin) break
        if (!match || end > match.index + match[0].length)
          match = newMatch
        from = newMatch.index + 1
      }
      return match
    }
  
    function searchRegexpBackward(doc, regexp, start) {
      regexp = ensureFlags(regexp, "g")
      for (var line = start.line, ch = start.ch, first = doc.firstLine(); line >= first; line--, ch = -1) {
        var string = doc.getLine(line)
        var match = lastMatchIn(string, regexp, ch < 0 ? 0 : string.length - ch)
        if (match)
          return {from: Pos(line, match.index),
                  to: Pos(line, match.index + match[0].length),
                  match: match}
      }
    }
  
    function searchRegexpBackwardMultiline(doc, regexp, start) {
      if (!maybeMultiline(regexp)) return searchRegexpBackward(doc, regexp, start)
      regexp = ensureFlags(regexp, "gm")
      var string, chunkSize = 1, endMargin = doc.getLine(start.line).length - start.ch
      for (var line = start.line, first = doc.firstLine(); line >= first;) {
        for (var i = 0; i < chunkSize && line >= first; i++) {
          var curLine = doc.getLine(line--)
          string = string == null ? curLine : curLine + "\n" + string
        }
        chunkSize *= 2
  
        var match = lastMatchIn(string, regexp, endMargin)
        if (match) {
          var before = string.slice(0, match.index).split("\n"), inside = match[0].split("\n")
          var startLine = line + before.length, startCh = before[before.length - 1].length
          return {from: Pos(startLine, startCh),
                  to: Pos(startLine + inside.length - 1,
                          inside.length == 1 ? startCh + inside[0].length : inside[inside.length - 1].length),
                  match: match}
        }
      }
    }
  
    var doFold, noFold
    if (String.prototype.normalize) {
      doFold = function(str) { return str.normalize("NFD").toLowerCase() }
      noFold = function(str) { return str.normalize("NFD") }
    } else {
      doFold = function(str) { return str.toLowerCase() }
      noFold = function(str) { return str }
    }
  
    // Maps a position in a case-folded line back to a position in the original line
    // (compensating for codepoints increasing in number during folding)
    function adjustPos(orig, folded, pos, foldFunc) {
      if (orig.length == folded.length) return pos
      for (var min = 0, max = pos + Math.max(0, orig.length - folded.length);;) {
        if (min == max) return min
        var mid = (min + max) >> 1
        var len = foldFunc(orig.slice(0, mid)).length
        if (len == pos) return mid
        else if (len > pos) max = mid
        else min = mid + 1
      }
    }
  
    function searchStringForward(doc, query, start, caseFold) {
      // Empty string would match anything and never progress, so we
      // define it to match nothing instead.
      if (!query.length) return null
      var fold = caseFold ? doFold : noFold
      var lines = fold(query).split(/\r|\n\r?/)
  
      search: for (var line = start.line, ch = start.ch, last = doc.lastLine() + 1 - lines.length; line <= last; line++, ch = 0) {
        var orig = doc.getLine(line).slice(ch), string = fold(orig)
        if (lines.length == 1) {
          var found = string.indexOf(lines[0])
          if (found == -1) continue search
          var start = adjustPos(orig, string, found, fold) + ch
          return {from: Pos(line, adjustPos(orig, string, found, fold) + ch),
                  to: Pos(line, adjustPos(orig, string, found + lines[0].length, fold) + ch)}
        } else {
          var cutFrom = string.length - lines[0].length
          if (string.slice(cutFrom) != lines[0]) continue search
          for (var i = 1; i < lines.length - 1; i++)
            if (fold(doc.getLine(line + i)) != lines[i]) continue search
          var end = doc.getLine(line + lines.length - 1), endString = fold(end), lastLine = lines[lines.length - 1]
          if (endString.slice(0, lastLine.length) != lastLine) continue search
          return {from: Pos(line, adjustPos(orig, string, cutFrom, fold) + ch),
                  to: Pos(line + lines.length - 1, adjustPos(end, endString, lastLine.length, fold))}
        }
      }
    }
  
    function searchStringBackward(doc, query, start, caseFold) {
      if (!query.length) return null
      var fold = caseFold ? doFold : noFold
      var lines = fold(query).split(/\r|\n\r?/)
  
      search: for (var line = start.line, ch = start.ch, first = doc.firstLine() - 1 + lines.length; line >= first; line--, ch = -1) {
        var orig = doc.getLine(line)
        if (ch > -1) orig = orig.slice(0, ch)
        var string = fold(orig)
        if (lines.length == 1) {
          var found = string.lastIndexOf(lines[0])
          if (found == -1) continue search
          return {from: Pos(line, adjustPos(orig, string, found, fold)),
                  to: Pos(line, adjustPos(orig, string, found + lines[0].length, fold))}
        } else {
          var lastLine = lines[lines.length - 1]
          if (string.slice(0, lastLine.length) != lastLine) continue search
          for (var i = 1, start = line - lines.length + 1; i < lines.length - 1; i++)
            if (fold(doc.getLine(start + i)) != lines[i]) continue search
          var top = doc.getLine(line + 1 - lines.length), topString = fold(top)
          if (topString.slice(topString.length - lines[0].length) != lines[0]) continue search
          return {from: Pos(line + 1 - lines.length, adjustPos(top, topString, top.length - lines[0].length, fold)),
                  to: Pos(line, adjustPos(orig, string, lastLine.length, fold))}
        }
      }
    }
  
    function SearchCursor(doc, query, pos, options) {
      this.atOccurrence = false
      this.doc = doc
      pos = pos ? doc.clipPos(pos) : Pos(0, 0)
      this.pos = {from: pos, to: pos}
  
      var caseFold
      if (typeof options == "object") {
        caseFold = options.caseFold
      } else { // Backwards compat for when caseFold was the 4th argument
        caseFold = options
        options = null
      }
  
      if (typeof query == "string") {
        if (caseFold == null) caseFold = false
        this.matches = function(reverse, pos) {
          return (reverse ? searchStringBackward : searchStringForward)(doc, query, pos, caseFold)
        }
      } else {
        query = ensureFlags(query, "gm")
        if (!options || options.multiline !== false)
          this.matches = function(reverse, pos) {
            return (reverse ? searchRegexpBackwardMultiline : searchRegexpForwardMultiline)(doc, query, pos)
          }
        else
          this.matches = function(reverse, pos) {
            return (reverse ? searchRegexpBackward : searchRegexpForward)(doc, query, pos)
          }
      }
    }
  
    SearchCursor.prototype = {
      findNext: function() {return this.find(false)},
      findPrevious: function() {return this.find(true)},
  
      find: function(reverse) {
        var result = this.matches(reverse, this.doc.clipPos(reverse ? this.pos.from : this.pos.to))
  
        // Implements weird auto-growing behavior on null-matches for
        // backwards-compatibility with the vim code (unfortunately)
        while (result && CodeMirror.cmpPos(result.from, result.to) == 0) {
          if (reverse) {
            if (result.from.ch) result.from = Pos(result.from.line, result.from.ch - 1)
            else if (result.from.line == this.doc.firstLine()) result = null
            else result = this.matches(reverse, this.doc.clipPos(Pos(result.from.line - 1)))
          } else {
            if (result.to.ch < this.doc.getLine(result.to.line).length) result.to = Pos(result.to.line, result.to.ch + 1)
            else if (result.to.line == this.doc.lastLine()) result = null
            else result = this.matches(reverse, Pos(result.to.line + 1, 0))
          }
        }
  
        if (result) {
          this.pos = result
          this.atOccurrence = true
          return this.pos.match || true
        } else {
          var end = Pos(reverse ? this.doc.firstLine() : this.doc.lastLine() + 1, 0)
          this.pos = {from: end, to: end}
          return this.atOccurrence = false
        }
      },
  
      from: function() {if (this.atOccurrence) return this.pos.from},
      to: function() {if (this.atOccurrence) return this.pos.to},
  
      replace: function(newText, origin) {
        if (!this.atOccurrence) return
        var lines = CodeMirror.splitLines(newText)
        this.doc.replaceRange(lines, this.pos.from, this.pos.to, origin)
        this.pos.to = Pos(this.pos.from.line + lines.length - 1,
                          lines[lines.length - 1].length + (lines.length == 1 ? this.pos.from.ch : 0))
      }
    }
  
    CodeMirror.defineExtension("getSearchCursor", function(query, pos, caseFold) {
      return new SearchCursor(this.doc, query, pos, caseFold)
    })
    CodeMirror.defineDocExtension("getSearchCursor", function(query, pos, caseFold) {
      return new SearchCursor(this, query, pos, caseFold)
    })
  
    CodeMirror.defineExtension("selectMatches", function(query, caseFold) {
      var ranges = []
      var cur = this.getSearchCursor(query, this.getCursor("from"), caseFold)
      while (cur.findNext()) {
        if (CodeMirror.cmpPos(cur.to(), this.getCursor("to")) > 0) break
        ranges.push({anchor: cur.from(), head: cur.to()})
      }
      if (ranges.length)
        this.setSelections(ranges, 0)
    })
  });